/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution23_2 {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) return null ;
        return merge(lists , 0 , lists.length-1) ;
    }
    private ListNode merge( ListNode[] list , int left , int right ){

         if(left >= right) return list[left] ; 
         int mid = left + (right-left)/2 ;
         // 1. 先分成两个区域, 递归两个区域
         ListNode list1 = merge(list , left , mid) ; 
         ListNode list2 = merge(list , mid+1 , right) ; 

         // 合并两个有序链表
         ListNode newHead = new ListNode() ;
         ListNode last = newHead ;
         ListNode cur1 = list1 , cur2 = list2 ;
         while(cur1 != null && cur2 != null){
             if(cur1.val < cur2.val){
                last.next = cur1 ;
                cur1 = cur1.next ;
             }else{
                last.next = cur2 ;
                cur2 = cur2.next ;
             }
             last = last.next ;
         }
         while(cur1 != null){
            last.next = cur1 ;
            cur1 = cur1.next ;
            last = last.next ;
         }
         while(cur2 != null){
            last.next = cur2 ;
            cur2 = cur2.next ;
            last = last.next ;
         }
        return newHead.next ;
    }
}